# 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
# 输入：l1 = [1,2,4], l2 = [1,3,4]
# 输出：[1,1,2,3,4,4]
#
# 输入：l1 = [], l2 = [0]
# 输出：[0]
from typing import Optional

from com.example.linked.common import *


class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        newHead = ListNode(-1)
        cur = newHead
        while list1 or list2:
            if list1 and list2:
                if list1.val < list2.val:
                    cur.next = list1
                    list1 = list1.next
                else:
                    cur.next = list2
                    list2 = list2.next
            elif not list1:
                cur.next = list2
                list2 = list2.next
            else:
                cur.next = list1
                list1 = list1.next
            cur = cur.next
        return newHead.next


if __name__ == '__main__':
    # 输入：l1 = [1,2,4], l2 = [1,3,4]
    # 输出：[1,1,2,3,4,4]
    l1 = getListNode(1, 2, 4)
    l2 = getListNode(1, 3, 4)
    res = Solution().mergeTwoLists(l1, l2)
    vistListNode(res)
